本场链接:Codeforces Round #586 (Div. 1 + Div. 2)
闲话
本场ABC都比较简单,D稍微有点麻烦.C这个傻逼题做复杂了,我原地退役.jpg.
A. Cards
题目大意:有很多张卡片上面写着zero或者one.现在把他们按字母分成了很多张小纸片,每个纸片上只有一个字母,问最大能拼出的序列是多少.
思路
显然一个zero必须要有一个z,一个one必须要有一个n.所以zero就有z的字母个数的数量,one就有n的字母个数的数量,直接统计输出,让one的先输出即可.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n;cin >> n;
string s;cin >> s;
int a = 0,b = 0;
for(int i = 0;i < n;++i)
if(s[i] == 'n') ++a;
else if(s[i] == 'r') ++b;
while(a--) cout << 1 << " ";
while(b--) cout << 0 << " ";
cout << endl;
return 0;
}
B. Multiplication Table
题目大意:最开始有一组长度为的序列.以及一个的矩阵M,的值这样给定:.现将M的主对角线上的所有元素擦除,要求输出一组原有的序列的构造方案使整个矩形的条件满足.
思路
显然对于每个不是的元素来说,可以这么干:得到他的值,而对于是的数,具体讨论一下也可以得到相应的构造方法,再次就不赘述了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1007;
int a[N][N];
int main()
{
int n;scanf("%d",&n);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
scanf("%d",&a[i][j]);
for(int i = 1;i <= n;++i)
{
if(i == 1) printf("%d ",(int)sqrt(1ll * a[1][2] * a[1][3] / a[2][3]));
else if(i == 2) printf("%d ",(int)sqrt(1ll * a[1][2] * a[2][3] / a[1][3]));
else if(i == 3) printf("%d ",(int)sqrt(1ll * a[1][3] * a[2][3] / a[1][2]));
else printf("%d ",(int)sqrt(1ll * a[1][i] * a[2][i] / a[1][2]));
}
return 0;
}
C. Substring Game in the Lesson
题目大意:有两个毒瘤在玩博弈游戏.这个游戏是在一个字符串的一个前缀子串上进行的.最开始的时候定义两个指针都在串的最后一位,每次可以这样移动指针:找到一个新的区间[l',r']使新划分出来的字符串字典序比原来的更小,满足这个条件就可以让原来的两个指针移动到对应的位置上.无法操作的人输.问是否先手必胜,先手为Ann,后手为Mike.要求输出对于所有可能的前缀子串的结果.
数据范围:
思路
由于题目的样例实在是太垃圾了,随便搞个长点的做一下试试:bcbacbaccaba.显然第一步一定是后手赢的,先手根本没法移动手上就一个b.再然后是bc,由于有一个更小的b在前面,这导致先手可以一步取完所有的元素而获得胜利.bcb就不行了,因为b和前面最小的字典序的b是一样的,导致Mike走到了一个必胜局面,再往后的一个bcba由于新出现的a比任何的都小,同样也是先手必败,因为先手一上来就动不了.之后再枚举下去,可以发现这个题第一点应该是线性递推的,第二点肯定跟字典序的相关大小有关.容易想到:如果当前的这一位新加的字符是最小的,先手就一定必败.因此这个题也就做出来了:只要手上是当前序列最小的,那么就是先手必败,否则可以直接掏空整个序列使对手必败.
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
string s;cin >> s;
int n;n = s.size();
char minc = 'z';
for(int i = 0;i < n;++i)
{
minc = min(minc,s[i]);
if(minc == s[i]) cout << "Mike\n";
else cout << "Ann\n";
}
return 0;
}
D. Alex and Julian
原题大意:给定一个个数没有重复的集合B.认为所有的整数都是一个点,并且点的数量是无限的,对于任意的两个点来说,如果则将两者之间连一条无向边.问集合B里最少删除掉多少个元素才能使整个图是一个二分图.要求输出删除的数量以及删除的具体元素有哪些.
数据范围:
思路
这题看起来就牛逼的很.先从简单情况入手:假如集合B里只有两个元素.想让他们两个构成一个奇环,需要什么样的条件.可以发现对于每个点开始来说,如果真的构成了一个环,这个环上的边的个数跟起点是谁没什么关系,不妨就假设是从开始的.那么如果构成了一个环,首先是存在两个最小的正整数使这样一个方程成立:其实也就是从出发走到了两个相同的点,这样就构成了一个环.那么这个环的长度就应该是,由于未知数比较多,考虑消元.对于这个式子来说,他的意思实际上就是最小公倍数,就是一个最小的正整数满足,所以长度之和就是,进一步变成.由于这是一个分数,所以先可以把所有的的因子除掉,那么怎样她才能是一个偶数的结果呢,显然下面一定是一个奇数了,因为里的偶因子不会多于上面的两者的偶因子的数量,所以关键在于上面的奇偶性,换句话说现在得到的的奇偶性和原来的和的奇偶性是相同的,显然如果这两者之间有一个是奇数,那么就不能得到偶数,也就是说两者包含的的因子的部分应该是相同的.比如#和的是相同的,两者都没有,是相同的,他们都有一个.但是和是不同的,因为一个是一个是.如果两个不同,则在去掉最多的公共的的因子之后,会出现一个奇数一个偶数,结果必然也还是一个奇数,就不符合了.经过这么一通分析,可以发现如果两个元素组成的环不是一个奇环,那么就要求这两个元素最后一位的位置是相同的才行.因此到这里就可以想到整个题的做法了,就是找出所有元素的最后一位的的位置再进行分组,在其中找出一组数量最多的就是答案所需要的一组,其他的全部删掉.
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N];
int main()
{
int n;scanf("%d",&n);
vector<ll> group[70];
for(int i = 1;i <= n;++i)
{
ll x;scanf("%lld",&x);
ll p = x;
int fnl = 0;
while(x)
{
if(x & 1)
{
group[fnl].push_back(p);
break;
}
++fnl;
x >>= 1;
}
}
// for(int i = 0;i < 70;++i)
// {
// if(!group[i].empty())
// {
// cout << i << endl;
// for(auto& v : group[i])
// cout << v << " " ;
// cout << endl;
// }
// }
int res = 0,pos = -1;
for(int i = 0;i < 70;++i)
{
if(res < group[i].size())
{
res = group[i].size();
pos = i;
}
}
printf("%d\n",n - res);
if(pos != -1)
{
// cout << "*" << pos << endl;
for(int i = 0;i < 70;++i)
if(i != pos && !group[i].empty())
{
for(auto& v : group[i])
printf("%lld ",v);
}
}
return 0;
}